from Table import *
import random


class LSH:
    __m_k = 0
    __m_d = 0
    __m_l = 0  # table数量
    __m_M = 0  # table size  100  也就是说每个表里面有多少个桶
    __m_FeatureDims = 0  # 维度    40
    __m_hashFun_level1Subset = []
    __m_hashFun_level2 = []
    __m_table = Table(0)
    __m_MaxValue = 0

    def __init__(self, maxValue, l, m, ratio, featureDims):  # 255,10,100,0.12,featureLength
        self.__m_k = int(maxValue * featureDims * ratio)  # 1224
        self.__m_d = maxValue * featureDims               # 10200
        self.__m_l = l                                    # table数量
        self.__m_M = m                                    # bucket数量
        self.__m_FeatureDims = featureDims                # 特征维数
        self.__m_MaxValue = maxValue                      # 最大值
        self.__m_table = Table(self.__m_M)                # 表结构
        for i in range(m):
            temp0 = []
            for j in range(featureDims):
                temp1 = []
                temp0.append(temp1)
            self.__m_hashFun_level1Subset.append(temp0)
        print(self.__m_hashFun_level1Subset)
        for i in range(self.__m_k):
            self.__m_hashFun_level2.append(random.randint(0, self.__m_M - 1))

    def __HashLevel2(self, value):
        bucketID = -1
        temp = 0
        for i in range(len(value)):
            temp += self.__m_hashFun_level2[i] * value[i]
        bucketID = temp % self.__m_M
        return bucketID

    def __Hash_level1(self, feature, tableID):
        value = []
        table = self.__m_hashFun_level1Subset[tableID]
        for i in range(len(table)):
            val0 = feature[i]
            one_num = 0
            zero_num = 0
            for j in range(len(table[i])):
                val1 = table[i][j] - self.__m_d * i
                if val1 < val0:
                    one_num += 1
                else:
                    zero_num += 1
            while one_num > 0:
                value.append(1)
                one_num -= 1
            while zero_num > 0:
                value.append(0)
                zero_num -= 1
        return value

    def __GetHashFun_level1(self):  # 生成一级哈希函数
        for i in range(self.__m_M):
            for j in range(self.__m_k):
                val = random.randint(0, self.__m_d - 1)  # 随即选取位置
                pos = int(val / self.__m_MaxValue)  # 对应原始特征的哪一维
                self.__m_hashFun_level1Subset[i][pos].append(val)
        print(self.__m_hashFun_level1Subset)

    def train(self, features):
        print('开始训练数据')
        self.__GetHashFun_level1()
        num = len(features)  # 特征个数
        for i in range(num):
            feature = features[i]
            for j in range(self.__m_l):  # tableID
                value = self.__Hash_level1(feature, j)
                bucketID = self.__HashLevel2(value)
                self.__m_table.addFeature(feature, bucketID, i)

    def __calcDist(self, feature0, feature1):
        dist = 0;
        length = len(feature0)
        for i in range(length):
            dist += abs(feature0[i] - feature1[i])
        return dist

    def search(self, feature):
        name = -1
        dist = -1
        minDist = 10000000
        buckets = []
        # hash获取所有候选bucket
        for i in range(self.__m_l):
            value = self.__Hash_level1(feature, i)
            bucketID = self.__HashLevel2(value)
            buckets.append(bucketID)
        print('查找时遍历的桶的个数为:%d' % len(buckets))
        for i in range(len(buckets)):  # 遍历候选bucket
            tempFeatures = self.__m_table.buckets[i].features
            tempName = self.__m_table.buckets[i].name
            num = len(tempFeatures)
            print('该桶含有的特征个数为：%d' % (num))
            for j in range(num):
                dist = self.__calcDist(feature, tempFeatures[j])
                if dist < minDist:
                    minDist = dist
                    name = tempName[j]
        return name, minDist
